package leetcode.code0430;

import java.util.Stack;

import leetcode.helper.tree.Node;

public class Solution extends Solution430 {

	@Override
	public Node flatten(Node head) {
		if (head == null)
			return head;
		Node pr = head;
		Node p = head;
		Stack<Node> s = new Stack<>();
		while (p != null || !s.isEmpty()) {
			if (p == null) {
				p = s.pop();
				pr.next = p;
				p.prev = pr;
				pr = p;
			}
			if (p.child == null) {
				p = p.next;// 没有child，p往后走
				if (p != null) {
					p.prev = pr;
					pr = p;
				}
			} else {// p.child != null
				if (p.next != null) {
					s.add(p.next);// next不为空，一会儿在连
				}
				p.next = p.child;
				p.child = null;
				p = p.next;
				p.prev = pr;
				pr = p;
			}
		}
		return head;
	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
	}

}
